package com.leetcode.www;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Creared with IntelliJ IDEA.
 * Description:请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
 *
 * 实现 MyStack 类：
 *
 * void push(int x) 将元素 x 压入栈顶。
 * int pop() 移除并返回栈顶元素。
 * int top() 返回栈顶元素。
 * boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
 *
 *
 * 注意：
 *
 * 你只能使用队列的基本操作 —— 也就是push to back、peek/pop from front、size 和is empty这些操作。
 * 你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列, 只要是标准的队列操作即可。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/implement-stack-using-queues

 * User:yxd
 * Date:2022-01-16
 * Time:23:25
 */
class MyStack {
    public Queue<Integer> qu1;//两个队列
    public Queue<Integer> qu2;

    public MyStack() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();

    }

    public void push(int x) {
        if(!qu1.isEmpty()){//谁不空放谁里面  两个都空 放第一个
            qu1.offer(x);
        }else if(!qu2.isEmpty()){
            qu2.offer(x);
        }else{
            qu1.offer(x);
        }
    }

    public int pop() {
        if(empty())return -1;
        if(!qu1.isEmpty()){//如果第一个不空 就出队 只剩下一个元素 这个元素就是要出栈的元素
            int a = qu1.size();
            for(int i =0;i < a - 1;i ++){
                qu2.offer(qu1.poll());
            }
            return qu1.poll();
        }
        if(!qu2.isEmpty()){//如果第二个不空 就出队 只剩下一个元素 这个元素就是要出栈的元素
            int a = qu2.size();
            for(int i =0;i < a - 1;i ++){
                qu1.offer(qu2.poll());
            }
            return qu2.poll();
        }
        return -1;
    }

    public int top() {
        if(empty())return -1;
        if(!qu1.isEmpty()){//如果第一个不空 就出队 只剩下一个元素 这个元素就是要出栈的元素
            int a = qu1.size();
            int val = 0;
            for(int i =0;i < a ;i ++){
                val = qu1.poll();
                qu2.offer(val);
            }
            return val;
        }
        if(!qu2.isEmpty()){
            int a = qu2.size();
            int val = 0;
            for(int i =0;i < a;i ++){
                val = qu2.poll();
                qu1.offer(val);
            }
            return val;
        }
        return -1;
    }

    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */
public class Normal225 {
    public static void main(String[] args) {
        MyStack obj = new MyStack();
        obj.push(1);
        obj.push(2);
        obj.push(3);
        obj.push(4);

        System.out.println(obj.pop());
        System.out.println(obj.top());
        System.out.println(obj.empty());
    }
}
